package Week.w150;

import java.util.*;

public class Solution3 {
    public int maxDistance(int[][] grid) {
        if (grid == null) return 0;
        int row = grid.length;
        int col = grid[0].length;
        /*记录所有陆地的位置*/
        List<Position> positions = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int value = grid[i][j];
                if (value == 1) {
                    positions.add(new Position(i, j));

                }
            }
        }

        int max = -1;
        if(positions.size()==0){
            return max;
        }
        /*遍历海水，计算海水距离陆地最近的地点，保存当前最大值*/
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]==0){
                    max=Math.max(max,getMinDistance(i,j,positions));
                }
            }
        }
        return max;

    }

    private int getMinDistance(int row,int col,List<Position> positions){
        int min=getDistance(row,col,positions.get(0));
        for(int i=1;i<positions.size();i++){
            min=Math.min(min,getDistance(row,col,positions.get(i)));
        }
        return min;
    }

    private int getDistance(int row,int col,Position position){
        return Math.abs(row-position.row)+ Math.abs(col-position.col);
    }

    class Position{
        public Integer row;

        public Integer col;

        public Position(Integer row, Integer col){
            this.row = row;
            this.col=col;
        }
    }

}
